Merging two polynomial linked lists using simultaneous traversal.

While finding the polynomial degree relies on a simple $O(1)$ lookup, the operation of addition requires merging the terms from two separate polynomial linked lists, $P_1(x)$ and $P_2(x)$. This process mimics the merge step of a merge-sort algorithm, traversing both lists simultaneously.

We use two primary pointers, $p$ for $P_1$ and $q$ for $P_2$, and systematically compare the exponents of their respective Polynomial_Term nodes:

  • Case 1: Exponents are equal.
    • Add the coefficients ($\text{coeff}_p + \text{coeff}_q$).
    • If the sum is non-zero, create a new node for the resultant list $R(x)$ with the new coefficient and the shared exponent.
    • Advance both pointers ($p$ and $q$).
  • Case 2: Exponent of $P_1$ is greater.
    • The term from $P_1$ is unique and must be preserved.
    • Copy the $P_1$ node (coefficient and exponent) directly to $R(x)$.
    • Advance only pointer $p$.
  • Case 3: Exponent of $P_2$ is greater.
    • The term from $P_2$ is unique.
    • Copy the $P_2$ node (coefficient and exponent) directly to $R(x)$.
    • Advance only pointer $q$.

Time Complexity

Since the algorithm visits every node in both lists exactly once, either to combine it or copy it, the total operation time is proportional to the total number of terms. If $P_1$ has $n$ terms and $P_2$ has $m$ terms, the addition complexity is $O(n+m)$.